import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        System.out.println(decodeString(4, new StringBuilder("ab")));
        System.out.println(s.decodeString("2[abc]3[cd]ef").equals("abcabccdcdcdef"));
    }

    public String decodeString(String s) {
        /**
         * 字符串解码
         * 解题思路：
         *  利用栈“后进先出”的特性模拟优先级处理，使用分情况讨论的思想进行操作
         * 涉及的一些操作及编码建议：
         *  需要提取数字、字符串，故建议使用while循环，可以更加明确地步进
         * 解法逻辑：
         *  将字符串追加到当前栈顶的字符串是正确处理嵌套字符最重要的一步，
         *  因为栈顶的字符串是外层的字符串，这样就完成了内层嵌套结构的解码并整合到外层结构中
         *  本解法也是这一步最为精妙
         *
         *  结合总体的思想：
         *      当我们遇见“[”会将内部未处理的字符串入栈，
         *      后续如果内部还存在待解码，按照逻辑，也会将其解码后尾插至字符串栈栈顶元素后，也就是前面未处理元素，解决了嵌套的问题
         *      当我们遇见“]”，又会将解码元素继续尾插字符串栈栈顶（避免栈为空，我们在创建字符串栈时就初始化了一个空字符串）
         *      最终结果就是字符串栈栈顶元素，形成逻辑闭环！*/
        // 1 预处理
        int n = s.length();
        // -- 由于后续需要往字符串栈顶后添加元素，故初始化时添加一个空字符串
        Stack<StringBuilder> strStack = new Stack<>();
        strStack.push(new StringBuilder(""));
        Stack<Integer> countStack = new Stack<>();

        // 2 遍历字符串
        int i = 0;
        while(i < n) {
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                // -数字
                // -- 提取数字后入次数栈
                int temp = 0;
                while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                    temp = temp * 10 + (s.charAt(i++) - '0');
                }
                countStack.push(temp);
            } else if(s.charAt(i) == '[') {
                // -- 提取右侧字符串后入字符串栈
                i++;
                StringBuilder tempStr = new StringBuilder();
                while(i < n && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                    tempStr.append(s.charAt(i++));
                }
                strStack.push(tempStr);
            } else if(s.charAt(i) == ']') {
                // -- 出栈解码后将结果尾插至字符串栈栈顶元素后
                StringBuilder tempStr = deco(countStack.pop(), strStack.pop());
                strStack.push(strStack.pop().append(tempStr));
                // <!-- 错误原因：i未步进导致空栈访问 -->
                i++;
            } else {
                // -字符串
                // -- 提取字符串并将其尾插至字符串栈栈顶元素后
                StringBuilder tempStr = new StringBuilder();
                while(i < n && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                    tempStr.append(s.charAt(i++));
                }
                strStack.push(strStack.pop().append(tempStr));
            }
        }
        return strStack.pop().toString();
    }

    public static StringBuilder deco(int count, StringBuilder s) {
        /**
         * 解码字符串*/
        StringBuilder retStr = new StringBuilder();
        for(int i = 0; i < count; i++) {
            retStr.append(s);
        }
        return retStr;
    }
}
